//线性表
#include <stdlib.h>
#include <stdio.h>
#define Maxsize 100

//线性表结构体的静态定义
typedef struct sequenceList
{
	int data[Maxsize];
	int length;
}sequenceList;

//线性表结构体的动态定义————补充

//单链表结点的定义方法
typedef struct loneNode
{
	int data;
	struct loneNode *next;
}loneNode;


//双链表结点的定义方法
typedef struct doubleNode
{
	int data;
	struct doubleNode *prior;
	struct doubleNode *next;
}doubleNode;




int main(int argc, char *argv[]) {
	
	//线性表的基本概念
	//线性表————同类元素，组成的一个有限序列。
	//线性表的长度==元素的个数，可为零
	//除表头、表尾元素，其他元素都有且仅有一个前驱/后继
	
	
	//线性表的存储结构————顺序存储：顺序表 and 链式存储：链表
	//顺序表————元素存储在一片 连续的 空间中————利于随机访问————需要预先分配空间————插入新元素需要移动多个元素
	/*链表————结点（元素）==元素内容+下一个结点位置————不需要连续的空间但空间利用率低
		————只能逐个访问————空间可随时增减（空间的动态分配）————插入元素时，无须移动其他元素*/
	
	
	//链表的分类
	/*
	分为 带头节点的链表 and 不带头节点的链表
	他们的头结点都不存入信息————只看头指针head有没有指向 头结点/开始结点。
	*/
	//1、单链表————结点中，存储一个指针，指向后继————访问的方向是单一的，从头到尾，不能逆序——最后一个指针为空
	//2、循环单链表————单链表+最后一个指针指向 开始结点/头结点————效果：从任意结点开始，均可访问所有结点
	//3、双链表————结点中，存储两个指针，指向前驱后继————可以从头到尾，也可从尾到头地访问
	//4、循环双链表————双链表+开始结点与终端结点互相连接
	/*5、静态链表————创造一个结构体struct（data ； int a）,再创造一个结构体数组struct[],a存储下一个结构体的地址
				————效果：可以不按顺序地遍历数组中的元素。*/
	
	
	//顺序表的定义方法
	int A[Maxsize];
	int length;
	
	
	//以下三个结构体在最上面有
	//线性表结构体的定义
	typedef struct sequenceList
	{
		int data[Maxsize];
		int length;
	}sequenceList;
	
	//单链表结点的定义方法
	typedef struct loneNode
	{
		int data;
		struct loneNode *next;
	}loneNode;
	
	//双链表结点的定义方法
	typedef struct doubleNode
	{
		int data;
		struct doubleNode *prior;
		struct doubleNode *next;
	}doubleNode;
	
	
	
		//结点的内存需要用户自己开辟————开辟后，系统会自动自动返回一个地址，需要用户自己用指针型变量来接收。
	loneNode *No1 = (loneNode*)malloc(sizeof(loneNode));//记得添加malloc的头文件——include <stdlib.h>
	//接收地址的指针 = （空间存储的数据类型） 开辟空间（空间的大小）
	/*No1是指针名 ，我们也把其视为结点名
	  No1指向A结点		释放No1空间free（No1））*/
	
	
	
}

/*******顺序表的操作*******/
//在顺序表中————查找某一元素e
int findElem(sequenceList L,int e)
{
	for(int i=0;i<L.length;i++)
	{
		if(e==L.data[i])return i;
	}
	return -1;
}

//在顺序表中————在p位置上，插入新元素e
void insertElem(sequenceList *L,int p,int e)
{			//要改变顺序表，所以取地址，用指针
	for(int i=L->length-1;i>=p;i--)
		L->data[i+1]=L->data[i];
	
	L->data[p]=e;
	L->length++;
}

//在顺序表中————删除p位置上的元素
void deleteElem(sequenceList *L,int p)
{			//要改变顺序表，所以取地址，用指针
	for(int i=p;i<L->length-1;i++)
		L->data[i]=L->data[i+1];
	
	L->length--;
}


/*******顺序表的逆置问题*******/    //？？？
//将数组a[]中的元素——从start到end的元素，进行逆序
void reverseElem(int *a[],int start,int end)
{
	
	for(start =0;start<end;start++,end--)
	{
		int temp;
		temp = *a[start];
		*a[start] = *a[end];
		*a[end] = temp;
	}
}

//将数组a[n]的前k个元素保持原序，放在a[n]数组后面——其余元素的顺序没有要求
void moveToEnd(int *a[],int k)
{
	reverseElem(a,0,k-1);//先对前k个数组逆序
	int length = sizeof(*a)/sizeof(a[0]);//？？？
	reverseElem(a,0,length);//再对全部元素逆序————效果：前k个数组保持了原序，并安排在了后面
}

//最终问题————将a[n]数组中的元素向右移动p个单位
void moveRight_p(int *a[],int p)
{
	
	int length = sizeof(*a)/sizeof(a[0]);//？？？
	reverseElem(a,0,p-1);
	reverseElem(a,p,length);
	reverseElem(a,0,length);
}


/*******单链表的操作*******/
//单链表操作练习：A、B为两个单链表，元素从小到大排序————让A、B组成一个新链表C，元素一样从小到大排序。
void merge(loneNode *A,loneNode *B,loneNode **C)
{ //把头结点引入（头结点以指针命名），就相当于引入了一个链表————要通过形参改变实参，就要引入头结点的地址（指针的指针）
	//开辟空间————开辟的是辅助指针的空间，单链表结点的空间已经开辟了，不用重复开辟
	loneNode *a = (loneNode*)malloc(sizeof(loneNode));
	loneNode *b = (loneNode*)malloc(sizeof(loneNode));//指针a、b用来定位A、B中的结点，方便比较
	
	loneNode *c = (loneNode*)malloc(sizeof(loneNode));//用来建立各个结点的新联系，来创造单链表C
	//定义辅助指针
	a = A->next;
	b = B->next;
	c = (*C);
	
	while(a!=NULL&&b!=NULL)
	{
		if(a->data<=b->data){
			c->next=a;
			a=a->next;
			c=c->next;
		}
		else{
			c->next=b;
			b=b->next;
			c=c->next;
		}
	}
	
	if(a==NULL)c->next=b;
	if(b==NULL)c->next=a;
}


//建立单链表————尾插法————新结点从尾部接入————按数组原本的顺序，组织数据
void createLoneList_tail(loneNode **L,int a[],int n)
{					//用单链表储存a[]数组中的元素
	//开辟空间————创造辅助指针————用来建立各个结点的联系
	struct loneNode *p = (loneNode *)malloc(sizeof(loneNode));
	p = (*L);
	
	for(int i=0;i<n;i++)
	{
		//开辟空间，构造新结点————存储数据
		struct loneNode *s = (loneNode *)malloc(sizeof(loneNode));
		s->data = a[i];
		p->next = s;//利用辅助指针，将新结点纳入链表中
		p=p->next;//移动位置，方便下一次连接
	}
	p->next = NULL;
}


//建立单链表————头插法————实现a[]中元素的逆向排序
void createLoneList_head(loneNode **L,int a[],int n)
{
	//开辟空间————创造辅助指针————用来建立各个结点的联系
	struct loneNode *p = (loneNode *)malloc(sizeof(loneNode));
	p = (*L);
	
	for(int i=0;i<n;i++)
	{
		struct loneNode *s=(loneNode *)malloc(sizeof(loneNode));
		s->data=a[i];
		//头插法的精髓————从头部插入
		s->next=p->next;
		p->next=s;
		
		p=p->next;//移动位置，方便下一次连接
	}
	p->next=NULL;
}

//删除————单链表中的第n个结点
void deleteNode(loneNode **L,int n)
{
	struct loneNode *p=(loneNode *)malloc(sizeof(loneNode));//创造一个辅助指针，用来连接各个结点
	struct loneNode *q=(loneNode *)malloc(sizeof(loneNode));//创造一个指针，用来定位要删除的n结点
	
	p=(*L);
	q=(*L);
	//让p、q指向第n-1个结点
	for(int i=0;i<n;i++)
	{
		p=p->next;
		q=q->next;
	}
	//删除操作。并对n的结点的前驱、后继——建立新连接
	q=p->next;
	p->next=p->next->next;
	free(q);
}



/*******双链表的操作*******/
//建立一个双链表————利用a[]中的元素——利用尾插法————头插法则类推适用
void createDoubleList(doubleNode **L,int a[],int n)
{
	struct doubleNode *p=(doubleNode *)malloc(sizeof(doubleNode));//开辟一个空间，创造一个辅助指针，用来建立各个结点的联系
	p=(*L);
	
	for(int i=0;i<n;i++)
	{
		struct doubleNode *s=(doubleNode *)malloc(sizeof(doubleNode));//开辟一个空间，创造新的结点
		s->data = a[i];
		//建立双链接
		s->prior = p;
		p->next = s;
		p = s;
	}
	p->next = NULL;
}


//插入结点————在双链表中的第n个位置上，插入一个新结点，记录元素e
void insertDoubleNode(doubleNode **L,int n,int e)
{
	struct doubleNode *p = (doubleNode *)malloc(sizeof(doubleNode));//开辟一个空间，创造辅助指针p，用来建立新的链接
	p = (*L);
	
	struct doubleNode *s = (doubleNode *)malloc(sizeof(doubleNode));//开辟一个空间，创造一个新结点，用来存储e元素
	s->data = e;

	//找到第n-1个元素
	for(int i=0;i<n;i++)
	{
		p=p->next;
	}
	//建立四个新链接
	s->next = p->next;
	s->prior = p;
	p->next = s;
	s->next->prior = s;
}


//删除结点————删除双链表中的第n个结点
void deleteDoubleNode(doubleNode **L,int n)
{
	struct doubleNode *p = (doubleNode *)malloc(sizeof(doubleNode));//开辟一个空间，创造辅助指针p，用来建立新的链接
	p = (*L);
	
	struct doubleNode *s = (doubleNode *)malloc(sizeof(doubleNode));//开辟一个空间，创造一个指针，用来指向要删除的n结点
	s = (*L);
	//找到第n-1个结点
	for(int i=0;i<n;i++)
	{
		p = p->next;
		s = s->next;
	}
	s = s->next;//指到了第n个元素
	//建立新链接
	p->next->next->prior = p;
	p->next = p->next->next;
	free(s);
}



